//You are given a list of airline tickets where tickets[i] = [fromi, toi] repres
//ent the departure and the arrival airports of one flight. Reconstruct the itiner
//ary in order and return it. 
//
// All of the tickets belong to a man who departs from "JFK", thus, the itinerar
//y must begin with "JFK". If there are multiple valid itineraries, you should ret
//urn the itinerary that has the smallest lexical order when read as a single stri
//ng. 
//
// 
// For example, the itinerary ["JFK", "LGA"] has a smaller lexical order than ["
//JFK", "LGB"]. 
// 
//
// You may assume all tickets form at least one valid itinerary. You must use al
//l the tickets once and only once. 
//
// 
// Example 1: 
//
// 
//Input: tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]
//Output: ["JFK","MUC","LHR","SFO","SJC"]
// 
//
// Example 2: 
//
// 
//Input: tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["AT
//L","SFO"]]
//Output: ["JFK","ATL","JFK","SFO","ATL","SFO"]
//Explanation: Another possible reconstruction is ["JFK","SFO","ATL","JFK","ATL"
//,"SFO"] but it is larger in lexical order.
// 
//
// 
// Constraints: 
//
// 
// 1 <= tickets.length <= 300 
// tickets[i].length == 2 
// fromi.length == 3 
// toi.length == 3 
// fromi and toi consist of uppercase English letters. 
// fromi != toi 
// 
// Related Topics 深度优先搜索 图 欧拉回路 
// 👍 510 👎 0


package leetcode.editor.cn;

import java.util.*;

//Java：Reconstruct Itinerary
public class P332ReconstructItinerary {
    public static void main(String[] args) {
        Solution solution = new P332ReconstructItinerary().new Solution();
        // TO TEST
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        Map<String, PriorityQueue<String>> map = new HashMap<String, PriorityQueue<String>>();
        List<String> itinerary = new LinkedList<String>();

        public List<String> findItinerary(List<List<String>> tickets) {
            for (List<String> ticket : tickets) {
                String src = ticket.get(0), dst = ticket.get(1);
                if (!map.containsKey(src)) {
                    map.put(src, new PriorityQueue<String>());
                }
                map.get(src).offer(dst);
            }
            dfs("JFK");
            Collections.reverse(itinerary);
            return itinerary;
        }

        public void dfs(String curr) {
            while (map.containsKey(curr) && map.get(curr).size() > 0) {
                String tmp = map.get(curr).poll();
                dfs(tmp);
            }
            itinerary.add(curr);
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}